package chapter01;

public class Jump45 {
    /**
     * 递归+记忆化搜索
     * process(nums,pos,dp) 从pos位置到达终点的最少移动次数
     * 递归出口
     *      1) pos>=length-1 说明已经到达终点位置，后续不需要在进行移动
     *         return 0
     *      2) 从pos位置开始 移动步数为i->1~[pos] 求pos+i到达终点的最少移动次数
     *         min=min(min,1+process(nums,pos+i,dp))
     *         为了防止min+1溢出 min=MAX_VALUE-1
     *         最后只需将min返回
     * 优化:记忆化搜索
     *      给递归加上缓存 dp[pos]存放从pos到达终点的最少移动次数
     *      1) 如果dp[pos]!=0
     *          return dp[pos]
     *      2) 返回结果前 先加入缓存
     *         dp[pos]=min
     *         return dp[pos]
     */
    public int jump(int[] nums) {
        int[] dp=new int[nums.length];
        return process(nums,0,dp);
    }

    public int process(int[] nums,int pos,int[] dp){
        if(pos>=nums.length-1){
            return 0;
        }
        if(dp[pos]!=0){
            return dp[pos];
        }
        int min=Integer.MAX_VALUE-1;
        for(int i=nums[pos];i>=1;i--){
            min=Math.min(min,1+process(nums,i+pos,dp));
        }
        dp[pos]=min;
        return dp[pos];
    }

    /**
     *  贪心算法
     *  从pos跳跃一次走i步后下一次跳跃能到达最远位置 局部最优解->全局最优解
     *  当前来到pos位置 下一次跳跃起点为j==pos+i i->1~[pos]
     *  如何求局部最优解？
     *      j==pos+i i->1~[pos]
     *      求得max{j+[j]}时 j位置就是下一次跳跃的起始位置 因此需要一个变量记录下一次跳跃的位置
     *      在尝试跳跃的过程中j==length-1时 跳跃次数+1 可以直接返回跳跃次数
     *      在求得下一次跳跃起点后 跳跃次数+1
     */
    public int jump1(int[] nums) {
        if(nums.length<2){
            return 0;
        }
        int index=0;
        int jumpCount=0;
        while (index<nums.length-1){
            int maxStep=0;
            int nextIndex=index;
            for(int i=index+1;i<nums.length&&i<=index+nums[index];i++){
                if(i==nums.length-1){
                    jumpCount++;
                    return jumpCount;
                }
                if(maxStep<i+nums[i]){
                    maxStep=i+nums[i];
                    nextIndex=i;
                }
            }
            index=nextIndex;
            jumpCount++;
        }
        return jumpCount;
    }
}
